package com.factory.server.tsp;

/**
 * TSP.java This file is part of JaCoP.
 *
 * JaCoP is a Java Constraint Programming solver.
 *
 * Copyright (C) 2000-2008 Krzysztof Kuchcinski and Radoslaw Szymanek
 *
 * This program is free software: you can redistribute it and/or modify it under
 * the terms of the GNU Affero General Public License as published by the Free
 * Software Foundation, either version 3 of the License, or (at your option) any
 * later version.
 *
 * This program is distributed in the hope that it will be useful, but WITHOUT
 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
 * FOR A PARTICULAR PURPOSE. See the GNU Affero General Public License for more
 * details.
 *
 * Notwithstanding any other provision of this License, the copyright owners of
 * this work supplement the terms of this License with terms prohibiting
 * misrepresentation of the origin of this work and requiring that modified
 * versions of this work be marked in reasonable ways as different from the
 * original version. This supplement of the license terms is in accordance with
 * Section 7 of GNU Affero General Public License version 3.
 *
 * You should have received a copy of the GNU Affero General Public License
 * along with this program. If not, see <http://www.gnu.org/licenses/>.
 *
 */
import JaCoP.constraints.Circuit;
import JaCoP.constraints.Element;
import JaCoP.constraints.Sum;
import JaCoP.core.Domain;
import JaCoP.core.IntVar;
import JaCoP.core.Store;
import JaCoP.search.DepthFirstSearch;
import JaCoP.search.IndomainMin;
import JaCoP.search.MaxRegret;
import JaCoP.search.SelectChoicePoint;
import JaCoP.search.SimpleMatrixSelect;
import JaCoP.search.SimpleSolutionListener;
import JaCoP.search.SmallestDomain;
import com.factory.server.dto.EdgeDTO;
import java.util.List;

/**
 *
 * It models Travelling Salesman Problem (TSP).
 *
 * @author Radoslaw Szymanek
 *
 */
public class TSP extends Example {

    IntVar[][] varsMatrix;
    int[][] distance;
    int noCities;
    Domain[] solution;
    SimpleSolutionListener listener;

    @Override
    public void model() {

        // Creating constraint store
        store = new Store();
        varsMatrix = new IntVar[noCities][2];

        // Denotes a city to go to from
        // index city
        IntVar[] cities = new IntVar[noCities];
        // Denotes a cost of traveling between
        // index city and next city
        IntVar[] costs = new IntVar[noCities];

        for (int i = 0; i < cities.length; i++) {
            cities[i] = new IntVar(store, "cities[" + (i + 1) + "]", 1,
                    cities.length);
            costs[i] = new IntVar(store, "costs[" + (i + 1) + "]", 0, Integer.MAX_VALUE);
            varsMatrix[i][0] = costs[i];
            varsMatrix[i][1] = cities[i];
        }

        // Impose cuircuit constraint which makes sure
        // that array cities is a hamiltonian circuit
        store.impose(new Circuit(cities));

        // Computes a cost of traveling between ith city
        // and city[i]-th city
        for (int i = 0; i < cities.length; i++) {
            store.impose(new Element(cities[i], distance[i], costs[i]));
        }

        cost = new IntVar(store, "Cost", 0, Integer.MAX_VALUE);

        // Computes overall cost of traveling
        // simply sum of all costs
        store.impose(new Sum(costs, cost));

    }

    /**
     *
     * It uses MaxRegret variable ordering heuristic to search for a solution.
     *
     * @return true if there is a solution, false otherwise.
     *
     */
    public boolean searchMaxRegretForMatrixOptimal() {

        long T1, T2, T;
        T1 = System.currentTimeMillis();

        search = new DepthFirstSearch<IntVar>();

        // pivot variable is at index 0.
        SelectChoicePoint<IntVar> select = new SimpleMatrixSelect<IntVar>(varsMatrix,
                new MaxRegret<IntVar>(),
                new SmallestDomain<IntVar>(),
                new IndomainMin<IntVar>());

        boolean result = search.labeling(store, select, cost);
        listener = (SimpleSolutionListener) search.getSolutionListener();
        T2 = System.currentTimeMillis();
        T = T2 - T1;

        System.out.println("\n\t*** Execution time = " + T + " ms");

        return result;

    }

    public String run(TSP tsp) {
        tsp.model();

        if (tsp.searchMaxRegretForMatrixOptimal()) {
            System.out.println("Solution(s) found");
        }
        return this.listener.toString() + cost;
    }

    public void initialize(int numberOfCities, List<EdgeDTO> edgesList) {
        this.noCities = numberOfCities;
        this.distance = new int[numberOfCities][numberOfCities];

        for (EdgeDTO edgeDTO : edgesList) {
            distance[edgeDTO.getSource() - 1][edgeDTO.getTarget() - 1] = (int) edgeDTO.getCost();
        }
    }
    /**
     * It executes the program to solve this Travelling Salesman Problem.
     *
     * @param args no argument is used.
     */
//    public static void main(String args[]) {
//
//        TSP example = new TSP();
//
//        example.model();
//
//        if (example.searchMaxRegretForMatrixOptimal()) {
//            System.out.println("Solution(s) found");
//        }
//
//    }
}
